//
// Created by yyancy on 2019/11/10.
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


char *factor[10] = {"rock", "scissors", "paper"};

#define SIDE_LEN 10
char board[SIDE_LEN][SIDE_LEN];

// 表示8个方向,逆时针
int move[8][2] = {{0,  1},
                  {1,  1},
                  {1,  0},
                  {1,  -1},
                  {0,  -1},
                  {-1, -1},
                  {-1, 0},
                  {-1, 1}
};

int move2[4][2] = {{1,  0},
                   {0,  1},
                   {-1, 0},
                   {0,  -1},

};

int generate_val(int inclusive_start, int exclusive_end) {
    return (rand() % (exclusive_end - inclusive_start)) + inclusive_start;
}

int generate_side() {
    return generate_val(0, 2);
}

typedef struct {
    int x, y;
} position;


/**
 * 迷宫
 * @return
 */
int main() {

    srand((unsigned) time(NULL));
    for (int i = 0; i < SIDE_LEN; ++i) {
        for (int j = 0; j < SIDE_LEN; ++j) {
            if ((i == 1 && j == 1) || (i == 8 && j == 8)) {
                board[i][j] = '0';
            } else if (i == 0 || j == 0 || i == SIDE_LEN - 1 || j == SIDE_LEN - 1) {
                board[i][j] = '1';
            } else {
                board[i][j] = (char) (generate_side() + 48);
            }
        }
    }

    printf("随机产生的迷宫如下:\n");
    for (int i = 0; i < SIDE_LEN; ++i) {
        for (int j = 0; j < SIDE_LEN; ++j) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
    position stack[100];
    int top = 0;
    position p = {1, 1};
    stack[top] = p;
    board[1][1] = '.';
    do {
        p = stack[top];
        int x, y, i;
        for (i = 0; i < 8; ++i) {
            x = p.x + move[i][0];
            y = p.y + move[i][1];
            if (board[x][y] == '0') {
                p.x = x, p.y = y;
                stack[++top] = p;
                board[x][y] = '.';
                break;
            }
        }
        if (i == 8) {
            board[p.x][p.y] = '*';
            top--;
        }

    } while (top > 0 && (p.x != 8 || p.y != 8));


    printf("走过的迷宫如下:\n");
    for (int i = 0; i < SIDE_LEN; ++i) {
        for (int j = 0; j < SIDE_LEN; ++j) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }

    printf("\n");
    int stop;
    // 输出探路结果
    if (top <= 0) printf("结论:没有路径\n");
    else printf("结论:有路径\n");
    printf("输入1退出， 其他键继续。 请回答:");
    scanf("%c", &stop);
    if (stop == '1') {
        printf("再见!\n");
        return 0;

    }

}

